#include "my_malloc.h"
#include <math.h>
/**
	David Hendon
**/

/* You *MUST* use this macro when calling my_sbrk to allocate the 
 * appropriate size. Failure to do so may result in an incorrect
 * grading!
 */
#define SBRK_SIZE 2048

/* If you want to use debugging printouts, it is HIGHLY recommended
 * to use this macro or something similar. If you produce output from
 * your code then you will receive a 20 point deduction. You have been
 * warned.
 */
#ifdef DEBUG
#define DEBUG_PRINT(x) printf x
#else
#define DEBUG_PRINT(x)
#endif


/* make sure this always points to the beginning of your current
 * heap space! if it does not, then the grader will not be able
 * to run correctly and you will receive 0 credit. remember that
 * only the _first_ call to my_malloc() returns the beginning of
 * the heap. sequential calls will return a pointer to the newly
 * added space!
 * Technically this should be declared static because we do not
 * want any program outside of this file to be able to access it
 * however, DO NOT CHANGE the way this variable is declared or
 * it will break the autograder.
 */
void* heap;
int heap_size = 0;


/* our freelist structure - this is where the current freelist of
 * blocks will be maintained. failure to maintain the list inside
 * of this structure will result in no credit, as the grader will
 * expect it to be maintained here.
 * Technically this should be declared static for the same reasons
 * as above, but DO NOT CHANGE the way this structure is declared
 * or it will break the autograder.
 */
metadata_t* freelist[8];
/**** SIZES FOR THE FREE LIST ****
 * freelist[0] -> 16
 * freelist[1] -> 32
 * freelist[2] -> 64
 * freelist[3] -> 128
 * freelist[4] -> 256
 * freelist[5] -> 512
 * freelist[6] -> 1024
 * freelist[7] -> 2048
 */


void* my_malloc(size_t size)
{
	size_t size_total = size + sizeof(metadata_t);
	int arr_idx;
	/* stores return address of metadata */
	metadata_t * metadata_ptr = NULL;
	/* stores the return value */ 
	char* return_addr; 
	DEBUG_PRINT(("\tEntered Size: %d\n",size));
	if(size_total > SBRK_SIZE) {
		ERRNO = SINGLE_REQUEST_TOO_LARGE; 
		DEBUG_PRINT(("ERROR: Invalid Request: %d\n",size));
  		return NULL;
	}
	else {
		if(!heap || largest_freeblock() < size_total) {
			if(!expand_heap()) { /* error code already set, so it just returns null*/
				DEBUG_PRINT(("ERROR: Unable to expand the heap, heap_size=%d",heap_size));	
				return NULL;
			}
		}
		size_total = get_size(size_total);
		DEBUG_PRINT(("\tDetermined Size: %d\n", size_total));
		arr_idx = get_index(size_total);
		DEBUG_PRINT(("\tStart Index: %d\n", arr_idx));
		metadata_ptr = (metadata_t*)find_mem(arr_idx,size_total);
		metadata_ptr->size = size_total;
		return_addr = modPtr(metadata_ptr, sizeof(metadata_t));
		return return_addr;
	}
}
/*
This function is used to dynamically allocate entire arrays at a time. It takes in the number of elements to be
allocated in the array as well as the size of each element. It will use malloc to allocate a stretch of dynamic
memory appropriately sized for the user. Note that calloc also initializes this stretch of memory to 0.
Should the malloc call fail, it should return NULL and set the proper error code.
*/

void* my_calloc(size_t num, size_t size)
{
	char* addr = my_malloc(size*num);
	if(!addr) {
		ERRNO = OUT_OF_MEMORY;	
		DEBUG_PRINT(("ERROR: Out of Memory\n"));
  		return NULL;
	} else {
		/* Copy 0 to the first num characters of addr. Return addr*/
  		size_t i;
  		for (i = 0; i < num; i++, addr++) {
  	  		*addr = 0;
  		}
	}
  return (metadata_t*)addr;
}

void my_free(void* ptr) 
{ 	
	if(!ptr) {
		/* why pass in a null pointer? Jerk.. */
		DEBUG_PRINT(("ERROR: in my_free() Invalid Input: NULL\n"));
		return;	
	}
	metadata_t* pointer = (metadata_t*)modPtr(ptr,-1*sizeof(metadata_t));
	DEBUG_PRINT(("pointer->size=%d\n",pointer->size));
	if(pointer->size >= SBRK_SIZE) {
		pointer->in_use = 0;
		DEBUG_PRINT(("push_front:%d\n",push_front(pointer,7)));
		return;
	}
	int arr_idx;
	metadata_t* buddy = get_buddy(pointer);
	while(buddy_is_free(pointer,buddy)){
		pointer = (metadata_t*)combine(pointer,buddy);
		if(pointer->size == SBRK_SIZE)
			break;
		buddy = get_buddy(pointer);
	}	
	arr_idx = get_index(pointer->size);
	push_front(pointer,arr_idx);
}
/*
This function takes in two pointers, a source and a destination as well as a size_t that indicates the number of
bytes to be copied. The source and destination could overlap, so it is important to copy as if you copied all the
number of bytes to be copied from the source to a temporary buffer and then copied to the destination. 
*/
void* my_memmove(void* dest, const void* src, size_t num_bytes)
{
	unsigned char *dest_ptr = dest;
	const unsigned char *src_ptr = src;
	if(src_ptr!=dest) { /*if they are already equal, then just return*/
		/*<-----s-----> <-----d----->  start at end of s*/
		if((src_ptr+num_bytes) < dest_ptr) {
			for (dest_ptr += num_bytes, src_ptr += num_bytes; num_bytes--;){
      			*--dest_ptr = *--src_ptr;
			}
		/*<-----s--<==>--d----->       start at end of s*/
		} else if((src_ptr+num_bytes) > dest_ptr && (src_ptr+num_bytes) < (dest_ptr+num_bytes)){
  		for (dest_ptr += num_bytes, src_ptr += num_bytes; num_bytes--;){
      			*--dest_ptr = *--src_ptr;
			}
		/*<-----d--<==>--s----->       start at beginning of s*/
		} else if(src_ptr < (dest_ptr+num_bytes) && (src_ptr+num_bytes) > (dest_ptr+num_bytes)){
			while(num_bytes--) {
      			*dest_ptr++ = *src_ptr++;
			}
		/*<-----d-----> <-----s----->  start at beginning of s*/
		} else if(dest_ptr+num_bytes < src_ptr) {
			while(num_bytes--) {
      			*dest_ptr++ = *src_ptr++;
			}
		}
	}
  return dest;
}
/*
	finds memory for malloc
*/
void* find_mem(int arr_idx, int goal_size) {
	metadata_t *head = freelist[arr_idx]; 
	metadata_t *first;
	metadata_t *second;
	metadata_t *ret;
	if (head && head->size == goal_size) {
		/* found */
		ret = head;
		remove_front(head, arr_idx);
		ret->in_use = 1;
		DEBUG_PRINT(("\tFound Memory: \theap offset:%lu\n",(unsigned long)ret-(unsigned long)heap));
		return ret;
	} else if (head && head->size > goal_size) {
		/* split */
		first = head;
		remove_front(first, arr_idx); /* removes bigger block from the list */
		first->size = head->size >> 1;
		second = (metadata_t*) modPtr(first,first->size);	/* allocate*/
		second->size = first->size;
		first->in_use = second->in_use = 0;
		first->next = second;
		first->prev = NULL;
		second->prev = first;
		second->next = freelist[arr_idx-1]; /* appends the second one to the front of freelist */
		freelist[arr_idx-1] = first;				
		return find_mem(arr_idx-1, goal_size);
	} else if (arr_idx < 8) {
		/* go up a level*/
		return find_mem(arr_idx+1, goal_size);
	} 
	return NULL; /* it failed */
}
/*
	determines if buddy is free by comparing n+1 bits
*/
int buddy_is_free(metadata_t* block, metadata_t* buddy) {
	int block_ptr = (int)block - (int)heap;
	int buddy_ptr = (int)buddy - (int)heap;
	int n = get_index(block->size) + 4;
	if(((block_ptr & 1<<(n+1))==(buddy_ptr & 1<<(n+1)))) {	
		if(!block || !buddy || buddy->in_use)
			return 0;
		else 
			return 1;
	}
	return 0;
}

/*
	combines the two blocks 
	removes them from freelist
	and returns the address of the combined block
	if: they are both buddies, and free and adjacent
	and not in use
	returns if it was successful
*/
void* combine(metadata_t* block, metadata_t* buddy) {
	metadata_t* combined;
	int arr_idx = get_index(block->size);
	if(!block || !buddy || buddy->in_use) {
		DEBUG_PRINT(("NOTIFICATION: combine() did not combine the two blocks\n"));
		block->in_use = 0;
		return block;
	}
	if(correct_order(block, buddy)) { /* if block is starting, it becomes new block */
		DEBUG_PRINT(("correct order\n"));		
		combined = block;
	}
	else {  /* otherwise buddy becomes starting address*/
		DEBUG_PRINT(("incorrect order\n"));		
		combined = buddy;		
	}
	combined->size *= 2;
	combined->in_use = 0;
	remove_target(arr_idx,block);
	remove_target(arr_idx,buddy);
	combined->next = NULL; /* I don't like that this is here */
	return combined;
}

/*
	returns true is left is on the left and right is on the right
	false otherwise
	Preconditions: left & right are not null
*/
int correct_order(metadata_t* left, metadata_t* right) {
	int l_ptr = (int)left - (int)heap;
	int r_ptr = (int)right - (int)heap;
	int n = get_index(left->size);
	if((l_ptr & 1<<(n+1))==(r_ptr & 1<<(n+1))) {
		if(!(l_ptr & (1<<n)))  /*left is first*/
			return 1;
		else 		/* right is first */
			return 0; 
	}
	else {
		DEBUG_PRINT(("ERROR: in correct_order() These are not buddies."));
		return -1;
	}
}

/*
	gets block's buddy, if it is not in use
	otherwise returns NULL
*/
void* get_buddy(metadata_t* block) {
	int block_ptr = (int)block-(int)heap;
	int n = get_index(block->size) + 4;
	metadata_t* buddy;
	int buddy_ptr;
	buddy_ptr = block_ptr ^ (1UL << n); /*flips the n bit to get the buddy*/
	buddy_ptr += (int)heap;
	buddy = (metadata_t*)buddy_ptr;
	DEBUG_PRINT(("BUDDY Size: %d Heap Offset:%d \n",buddy->size,(int)buddy-(int)heap));
	if(!buddy || buddy->in_use || buddy->size != block->size) {
		if(!buddy)
			DEBUG_PRINT(("WARNING: in get_buddy() Buddy is null\n"));
		else if(buddy->in_use)
			DEBUG_PRINT(("WARNING: in get_buddy() Buddy is in use\n"));
		else if(buddy->size != block->size)
			DEBUG_PRINT(("WARNING: in get_buddy() block->size=%d != buddy->size=%d\n",block->size,buddy->size));
		return NULL;
	}
	else 
		return buddy;
}

/* 
	Sets up new heap
	returns whether successful
*/
int expand_heap() {
	metadata_t* new_heap = my_sbrk(SBRK_SIZE); 
		/* set up new heap */
	if(new_heap == (void*)-1 || !new_heap) {
		ERRNO = OUT_OF_MEMORY;
		return 0;
	}
	if (!heap) {
		heap = new_heap;
		DEBUG_PRINT(("NOTIFICATION: Heap Initialized heap_size=%d\n",heap_size));
	}
	else {
		DEBUG_PRINT(("NOTIFICATION: Heap Expanded heap_size=%d\n",heap_size));
	}
	new_heap->next = freelist[7];
	freelist[7] = (metadata_t*) heap;
	freelist[7]->prev = freelist[7]->next = NULL;
	freelist[7]->in_use = 0;
	freelist[7]->size = SBRK_SIZE;
	heap_size+=SBRK_SIZE;
	return 1;
}
/*================================

	LINKED LIST IMPLEMENTATION

==================================*/
/*
 removes a node to the front of the freelist
 return: whether or not it was sucessful
*/
int remove_front(metadata_t* head, int arr_idx) {
	if(!head) {
		return 0; /*already empty*/
	}
	else if(!head->next) { /* one element list */
		freelist[arr_idx] = 0;
		return 1;
	}
	else {
		freelist[arr_idx] = head->next;
		freelist[arr_idx]->prev = NULL;
		return 1;
	}
}

/*
	removes a node to the back of the freelist
	return: whether or not it was sucessful
*/
int remove_back(metadata_t* head) {
	if(!head) {
		return 0;
	}	
	else if(!head->next) { /* one element list */
		int arr_idx = get_index(head->size);
		freelist[arr_idx] = 0;
		return 1;
	}
	else {
		metadata_t* curr = head;
		while(curr->next->next) {
			curr = curr->next;
		}
		curr->next->prev = NULL;
		curr->next = NULL;
		return 2;
	}
}	
/*
	removes the target node from a list, 
	and returns 0 if it didn't find it or failed
*/
int remove_target(int arr_idx, metadata_t* target) {
	metadata_t* curr = freelist[arr_idx];
	if(!curr) {
		return 0;
	}	
	else if(curr==target) {
		remove_front(target, arr_idx);
		return 1;
	}
	else {
		while(curr->next) {
			if(curr->next==target) {
				curr->next = curr->next->next;
				curr->next->prev = curr;
				return 1;
			}
			curr = curr->next;
		}
	}
	return 0; 
}	

/*
	adds a node to the front of the freelist
	return: whether or not it was sucessful
*/
int push_front(metadata_t* newdata, int arr_idx) {
	metadata_t* head = freelist[arr_idx];	
	if(arr_idx < 0 || arr_idx > 7) 
		return 0;
	else if(!newdata) 
		return 0;
	else if(!head) { /* empty list */
		freelist[arr_idx]=newdata;
		return 1;
	} else {
		head->prev = newdata;
		newdata->next = head;
		head = newdata;
		return 2;
	}

}

/*
	adds a node to the back of the freelist
	return: whether or not it was sucessful
*/
int push_back(metadata_t* newdata, int arr_idx) {
	if(arr_idx < 0 || arr_idx > 7) 
		return 0;
	else if(!newdata) 
		return 0;
	else {
		metadata_t* curr = freelist[arr_idx];
		while(curr->next) {
			curr = curr->next;
		}
		curr->next = newdata;
		newdata->prev = curr;
		return 1;
	}
}

/*
	helper to avoid pointer arithmetic issues
*/
void *modPtr(void *ptr, int num_bytes) {
   return (void*)(((char*)ptr)+num_bytes);
}

int get_size(size_t size) {
	if(size <=0 || size > SBRK_SIZE)
		return 0; /* if it fails */
	else if(size <= 16)
		return 16;
	else if(size <= 32)
		return 32;
	else if(size <= 64)
		return 64;
	else if(size <= 128)
		return 128;
	else if(size <= 256)
		return 256;
	else if(size <= 512)
		return 512;
	else if(size <= 1024)
		return 1024;
	else if(size <= 2048)
		return 2048;
	else
		return 0;
}

int get_index(size_t size) {
    switch (size) {
        case 16: return 0;
        case 32: return 1;
        case 64: return 2;
        case 128: return 3;
        case 256: return 4;
        case 512: return 5;
        case 1024: return 6;
        case 2048: return 7;
        default: return -1;
    }
}
/* 
	determines the largest available block in memory 
*/
int largest_freeblock() {
	metadata_t* curr;
	for(int i = 7; i >= 0; i--) {
		curr = freelist[i];
		if(curr)
			return curr->size;
	}
	return 0;
}
/*
	prints freelist
*/
void print_freelist() {
	metadata_t* curr;
	for(int i = 7; i >= 0; i--) {
		DEBUG_PRINT(("\nfreelist[%d]:",i));
		curr = freelist[i];
		while(curr) {
			DEBUG_PRINT(("[%d]->",curr->size));
			curr=curr->next;
		}
	}
	DEBUG_PRINT(("\n"));
}
